ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpb/labyrinth/main.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <cassert>
   4 #include <cstdio>
   5
   6 using namespace std;
   7
   8 #define forsn(i, s, n)  for (int i = (s); i < (n); i++)
   9 #define forn(i, n)      forsn (i, 0, n)
  10
  11 typedef vector<bool> vbool;
  12 typedef vector<vbool> vvbool;
  13
  14 typedef int Node;
  15 int rows;
  16 int cols;
  17 vvbool mapa;
  18
  19 #define node(r, c)              ((r) << 12 | (c))
  20 #define node_row(v)             ((v) >> 12)
  21 #define node_col(v)             ((v) & 0xfff)
  22
  23 #define NONE                    0xffffffff
  24
  25 Node vecino(bool ns, Node v) {
  26 #define sig(x)  ((x) ? 1 : -1)
  27         const int r = node_row(v) - ns, c = node_col(v);
  28         if (r < 0 || r >= rows) return NONE;
  29         const int cc = c + sig(ns ^ mapa[r][c]);
  30         if (cc < 0 || cc >= cols) return NONE;
  31         const int rr = node_row(v) + sig(ns) * -!(mapa[r][c] ^ mapa[r][cc]);
  32         if (rr < 0 || rr > rows) return NONE;
  33         return node(rr, cc);
  34 }
  35
  36 int resolver() {
  37 #define marcado(v)      (_marcas[node_row(v)][node_col(v)])
  38 #define marcar(v)       (_marcas[node_row(v)][node_col(v)] = true)
  39         int cant = 0;
  40         vvbool _marcas(rows + 1, vbool(cols, false));
  41         forn (c, cols) {
  42                 Node v = node(0, c);
  43
  44                 if (marcado(v)) continue;
  45                 marcar(v);
  46
  47                 for (;;) {
  48                         Node w = NONE;
  49                         forn (direction, 2) {
  50                                 Node vv = vecino(direction, v);
  51                                 if (vv == NONE || marcado(vv)) continue;
  52                                 assert(w == NONE);
  53                                 w = vv;
  54                         }
  55                         if (w == NONE) break;
  56                         if (node_row(w) == rows) {
  57                                 cant++;
  58                                 break;
  59                         }
  60                         marcar(w);
  61                         v = w;
  62                 }
  63         }
  64         return cant;
  65 }
  66
  67 int main() {
  68         int ncases;
  69         cin >> ncases;
  70
  71         forn (i, ncases) {
  72                 cin >> cols >> rows;
  73                 mapa = vvbool(rows, vbool(cols));
  74                 forn (r, rows) {
  75                         forn (c, cols) {
  76                                 char mapa_rc;
  77                                 cin >> mapa_rc;
  78                                 mapa[r][c] = (mapa_rc == '\\');
  79                         }
  80                 }
  81
  82                 cout << resolver() << endl;
  83         }
  84
  85         return 0;
  86 }